package touchtouch.geometry;

import java.util.Stack;
import java.util.Vector;

/**
 * grahamScan.java
 * Mark F. Hulber
 * May 1996
 * 
 * grahamScan implements the Graham Scan convex hull algorithm.Given
 * a vector containing points it will return a vector of points forming
 * the convex hull of the input.This class relies on extensions to the
 * point class called newPoints.grahamScan does not gin computing the
 * convex hull until three points have been provided.
 * 
 * adaptation by Matthias Mailliard
 * September 2008
 * 
 */

public class GrahamScanConvexHull {

	public Vector <newPoint> doGraham(Vector<newPoint> input_polygon) {
		Vector	<newPoint> convexPolygon	= new Vector	<newPoint> (100, 100);
		Stack	<newPoint> stk		= new Stack	<newPoint> ();
		Vector	<newPoint> s		= new Vector	<newPoint> (100, 100);
		
		int m = 0; 
		newPoint temp, temp2;
		int n = input_polygon.size();
		int a, i;
		if (n > 9) {System.out.println("taille "+n);
			s.removeAllElements();
			s = (Vector<newPoint>) input_polygon.clone();
			for (i = 1; i < n; i++)
				if ( s.elementAt(i).y < s.elementAt(m).y || 
					( (s.elementAt(i).y == s.elementAt(m).y) &&
					(s.elementAt(i)).x < s.elementAt(m).x) )
					m = i;
			temp = s.elementAt(0);
			s.setElementAt(s.elementAt(m),0);
			s.setElementAt(temp, m);
		 
			// stage 2
			temp2 = s.elementAt(0);
			for (i = 2; i < n; i++) {
				for (int j = n-1; j >= i; j --) {
					if (temp2.polarCmp(s.elementAt(j-1), s.elementAt(j)) == 1) {
						temp = s.elementAt(j-1);
						s.setElementAt(s.elementAt(j),j-1);
						s.setElementAt(temp, j);
					}
				}
			}
			for (i = 1; s.elementAt( i + 1 ).classify( s.elementAt(0), s.elementAt(i) ) == 3 ; i++) ; 
			stk.removeAllElements();
			stk.push(s.elementAt(0));
			stk.push(s.elementAt(i));
			
			boolean blah;
			for (i = i+1; i < n; i++) {
				blah = true;
				while ( blah && !stk.isEmpty() ) {
					temp2 = stk.pop();
					if (!stk.isEmpty() && s.elementAt(i).classify(stk.peek(), temp2 ) == 0) {
						stk.push(temp2);
						blah = false;
					}
				}
				stk.push((newPoint)s.elementAt(i));
			}
			
			convexPolygon.removeAllElements();
			
			while (!stk.empty())
				convexPolygon.addElement(stk.pop());
			return convexPolygon;
		}
		return null;
	}
}
